﻿//59. 螺旋矩阵 II
//给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。


class Solution {
public:
    vector<vector<int>> dir = { {0,1},{1,0},{0,-1},{-1,0} };  // 右 下 左 上
    vector<vector<int>> generateMatrix(int n)
    {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int cnt = 1;
        int x = 0, y = 0;
        int d = 0;
        while (cnt <= n * n)
        {
            ans[x][y] = cnt;
            cnt++;
            //越界或已访问
            int nextx = dir[d][0] + x;
            int nexty = dir[d][1] + y;
            if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= n || ans[nextx][nexty])
            {
                d++;
                d %= 4;
                nextx = dir[d][0] + x;
                nexty = dir[d][1] + y;
            }
            x = nextx, y = nexty;
        }
        return ans;
    }
};